๐Ÿ‘ฉโ€๐Ÿ’ป 42894. ๋ธ”๋ก ๊ฒŒ์ž„

@Seongukbaek Posted June 05, 2022 ยท Updated June 05, 2022 ยท 5 min read

๋ฌธ์ œ

Programmers - ๋ธ”๋ก ๊ฒŒ์ž„

๐Ÿ“ Logic

public void findRemovableBlock() { int count; // ๋” ์ด์ƒ ์‚ญ์ œ ๊ฐ€๋Šฅํ•œ ๋ธ”๋ก์ด ์—†์„ ๋•Œ๊นŒ์ง€ ์ง„ํ–‰ do { count = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // ๊ฐ€๋กœ ๋˜๋Š” ์„ธ๋กœ ๋ฒ”์œ„์˜ ์ง์‚ฌ๊ฐํ˜• ๋ธ”๋ก ์—ฌ๋ถ€ ํ™•์ธ if ((i <= N - 2 && j <= N - 3 && find(i, j, 2, 3)) || (i <= N - 3 && j <= N - 2 && find(i, j, 3, 2))) count++; } } removableBlocks += count; } while(count != 0); }
  • ์ด์ค‘ for๋ฌธ์œผ๋กœ ๋ณด๋“œ๋ฅผ ํ™•์ธํ•˜๋ฉด์„œ, 2x3 ๋ฒ”์œ„์™€ 3x2 ๋ฒ”์œ„๋ฅผ ํ™•์ธํ•˜์—ฌ ๊ฒ€์ • ๋ธ”๋ก 2๊ฐœ๋กœ ์‚ญ์ œํ•  ์ˆ˜ ์žˆ๋Š” ๋ธ”๋ก์˜ ์ˆ˜๋ฅผ ์นด์šดํŠธํ•œ๋‹ค.
private boolean find(int x, int y, int h, int w) { // ๋นˆ ๊ณต๊ฐ„์„ ์นด์šดํŠธ, ๋นˆ ๊ณต๊ฐ„์€ 2๊ฐœ๊นŒ์ง€๋งŒ ๊ฐ€๋Šฅํ•˜๋‹ค. ๋ธ”๋ก ๋ฒ”์œ„์˜ ํฌ๊ธฐ๋Š” 6์ด๊ณ  ๋ธ”๋ก์˜ ํฌ๊ธฐ๋Š” 4์ด๊ธฐ ๋•Œ๋ฌธ int emptyCount = 0; // ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๋ธ”๋ก ๋ฒˆํ˜ธ๋ฅผ ์ €์žฅ, ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๊ฒฝ์šฐ์—๋Š” ์ด ๊ฐ’๊ณผ ๋ชจ๋‘ ๋™์ผํ•ด์•ผ ํ•จ int lastNum = -1; for (int i = x; i < x + h; i++) { for (int j = y; j < y + w; j++) { // ๋นˆ ๊ณต๊ฐ„์ธ ๊ฒฝ์šฐ if (board[i][j] == 0) { if (!canFill(i, j)) return false; if (++emptyCount > 2) return false; } else { // ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๋ธ”๋ก ๋ฒˆํ˜ธ๊ฐ€ ์žˆ๊ณ , ํ˜„์žฌ ์˜์—ญ๊ณผ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ๋ผ๋ฉด ๊ฐ™์€ ๋ธ”๋ก์ด ์•„๋‹ˆ๋ฏ€๋กœ ์ข…๋ฃŒ if (lastNum != -1 && lastNum != board[i][j]) return false; lastNum = board[i][j]; } } } removeBlock(x, y, h, w); return true; }
  • ํ˜„์žฌ ์œ„์น˜์™€ ๊ฐ€๋กœ, ์„ธ๋กœ ๋ฒ”์œ„๋ฅผ ๊ฐ€์ง€๊ณ  ํ•ด๋‹น ๋ฒ”์œ„ ๋‚ด์˜ ๋นˆ ๊ณต๊ฐ„์˜ ๊ฐœ์ˆ˜์™€ ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๋ธ”๋ก์˜ ๋ฒˆํ˜ธ๋ฅผ ์ €์žฅํ•œ๋‹ค.

    • ๋นˆ ๊ณต๊ฐ„์˜ ๊ฐœ์ˆ˜๊ฐ€ 3๊ฐœ ์ด์ƒ์ผ ๊ฒฝ์šฐ ์ข…๋ฃŒํ•œ๋‹ค.
    • ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๋ธ”๋ก ๋ฒˆํ˜ธ์™€ ๊ฐ™์ง€ ์•Š์€ ๋ธ”๋ก ๋ฒˆํ˜ธ๊ฐ€ ๋‚˜์˜จ ๊ฒฝ์šฐ, ๋™์ผํ•œ ๋ธ”๋ก์ด ์•„๋‹ˆ๋ฏ€๋กœ ์ข…๋ฃŒํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Board { int N; int[][] board; // ์ง€์šธ ์ˆ˜ ์žˆ๋Š” ๋ธ”๋ก์˜ ์ˆ˜ int removableBlocks = 0; public Board(int[][] board) { this.N = board.length; this.board = board; } public void findRemovableBlock() { int count; // ๋” ์ด์ƒ ์‚ญ์ œ ๊ฐ€๋Šฅํ•œ ๋ธ”๋ก์ด ์—†์„ ๋•Œ๊นŒ์ง€ ์ง„ํ–‰ do { count = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // ๊ฐ€๋กœ ๋˜๋Š” ์„ธ๋กœ ๋ฒ”์œ„์˜ ์ง์‚ฌ๊ฐํ˜• ๋ธ”๋ก ์—ฌ๋ถ€ ํ™•์ธ if ((i <= N - 2 && j <= N - 3 && find(i, j, 2, 3)) || (i <= N - 3 && j <= N - 2 && find(i, j, 3, 2))) count++; } } removableBlocks += count; } while(count != 0); } private boolean find(int x, int y, int h, int w) { // ๋นˆ ๊ณต๊ฐ„์„ ์นด์šดํŠธ, ๋นˆ ๊ณต๊ฐ„์€ 2๊ฐœ๊นŒ์ง€๋งŒ ๊ฐ€๋Šฅํ•˜๋‹ค. ๋ธ”๋ก ๋ฒ”์œ„์˜ ํฌ๊ธฐ๋Š” 6์ด๊ณ  ๋ธ”๋ก์˜ ํฌ๊ธฐ๋Š” 4์ด๊ธฐ ๋•Œ๋ฌธ int emptyCount = 0; // ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๋ธ”๋ก ๋ฒˆํ˜ธ๋ฅผ ์ €์žฅ, ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๊ฒฝ์šฐ์—๋Š” ์ด ๊ฐ’๊ณผ ๋ชจ๋‘ ๋™์ผํ•ด์•ผ ํ•จ int lastNum = -1; for (int i = x; i < x + h; i++) { for (int j = y; j < y + w; j++) { // ๋นˆ ๊ณต๊ฐ„์ธ ๊ฒฝ์šฐ if (board[i][j] == 0) { if (!canFill(i, j)) return false; if (++emptyCount > 2) return false; } else { // ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹Œ ๋ธ”๋ก ๋ฒˆํ˜ธ๊ฐ€ ์žˆ๊ณ , ํ˜„์žฌ ์˜์—ญ๊ณผ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ๋ผ๋ฉด ๊ฐ™์€ ๋ธ”๋ก์ด ์•„๋‹ˆ๋ฏ€๋กœ ์ข…๋ฃŒ if (lastNum != -1 && lastNum != board[i][j]) return false; lastNum = board[i][j]; } } } removeBlock(x, y, h, w); return true; } // ํ•ด๋‹น ๊ณต๊ฐ„์„ ์ฑ„์šธ ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜, ํ•ด๋‹น ํ–‰์˜ ์œ— ํ–‰๊นŒ์ง€๊ฐ€ ๋น„์–ด์žˆ๋Š”์ง€ ํ™•์ธ private boolean canFill(int x, int y) { for (int i = 0; i < x; i++) if (board[i][y] != 0) return false; return true; } // ๋ธ”๋ก ์‚ญ์ œ private void removeBlock(int x, int y, int h, int w) { for (int i = x; i < x + h; i++) for (int j = y; j < y + w; j++) board[i][j] = 0; } public int getCount() { return removableBlocks; } } class Solution { public int solution(int[][] board) { Board b = new Board(board); b.findRemovableBlock(); return b.getCount(); } }

โœ๏ธ Review

  • ๋ฌธ์ œ ์ž์ฒด ์ดํ•ด๋Š” ์–ด๋ ต์ง€ ์•Š์•˜์ง€๋งŒ, ๊ตฌํ˜„์ด ์ข€ ๋นก์…Œ๋‹ค.
  • ์‚ญ์ œ๊ฐ€ ๊ฐ€๋Šฅํ•œ์ง€ ์•„๋‹Œ์ง€ ํ™•์ธํ•˜๋Š” ๋กœ์ง์ด ์ค‘์š”ํ–ˆ๋‹ค.
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€